/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30/FONT#10=ZERO30
␈↓ α∧␈↓␈↓ u1


␈↓ α∧␈↓α␈↓ ∧≤Proposal for Basic Research in Artificial Intelligence

␈↓ α∧␈↓␈↓ αTThis is an accomplishment-based renewal proposal.

␈↓ α∧␈↓␈↓ αTFour␈αpapers,␈αone␈αreport,␈αone␈αjoint␈αpaper␈αaccepted␈αfor␈αpublication␈αand␈αone␈αpaper␈αsubmitted
␈↓ α∧␈↓for publication are the published basis for this renewal.

␈↓ α∧␈↓The papers are:

␈↓ α∧␈↓␈↓αMcCarthy,␈αJohn␈α(1979)␈↓:␈α
"Ascribing␈αMental␈αQualities␈αto␈α
Machines"␈αin␈α␈↓↓Philosophical␈αPerspectives␈α
in
␈↓ α∧␈↓↓Artificial Intelligence␈↓, Ringle, Martin (ed.), Harvester Press, July 1979.

␈↓ α∧␈↓Computer␈α∂programs␈α⊂vary␈α∂much␈α∂more␈α⊂than␈α∂people␈α∂in␈α⊂the␈α∂extent␈α∂and␈α⊂nature␈α∂of␈α⊂the␈α∂intentional
␈↓ α∧␈↓properties␈α∩that␈α⊃may␈α∩be␈α∩usefully␈α⊃ascribed␈α∩to␈α⊃them.␈α∩ This␈α∩paper␈α⊃outlines␈α∩criteria␈α∩for␈α⊃ascribing
␈↓ α∧␈↓specific␈α∂mental␈α∂qualities,␈α⊂e.g␈α∂specific␈α∂beliefs␈α⊂and␈α∂goals,␈α∂to␈α⊂computer␈α∂programs␈α∂and␈α⊂machines␈α∂in
␈↓ α∧␈↓general.␈α
 A␈αpopular␈α
version␈αappeared␈α
in␈α
␈↓↓Psychology␈αToday␈↓,␈α
December␈α1983.␈α
 John␈αPerry␈α
expressed
␈↓ α∧␈↓interest in including one or the other in his forthcoming ␈↓↓Oxford Readings in Philosophy␈↓ volume.

␈↓ α∧␈↓␈↓αMcCarthy,␈α∪John␈α∩(1979)␈↓:␈α∪"First␈α∩Order␈α∪Theories␈α∩of␈α∪Individual␈α∩Concepts␈α∪and␈α∪Propositions",␈α∩in
␈↓ α∧␈↓Michie, Donald (ed.) ␈↓↓Machine Intelligence 9␈↓, (University of Edinburgh Press, Edinburgh).

␈↓ α∧␈↓This␈α⊂paper␈α⊂presents␈α⊂a␈α⊂variety␈α⊂of␈α⊂formalisms␈α⊂for␈α⊂expressing␈α⊂facts␈α⊂about␈α⊂knowledge␈α⊂and␈α∂belief.
␈↓ α∧␈↓What␈α
was␈α
new␈α
was␈α
sticking␈α
to␈α
first␈α
order␈α
logic␈α
but␈α
keeping␈α
the␈α
objects␈α
of␈α
belief,␈α
etc.␈α
as␈αabstract
␈↓ α∧␈↓objects␈αrather␈αthan␈αmaking␈αthem␈αsentences.␈α With␈αthe␈αaid␈αof␈αnotions␈αof␈αstandard␈αconcepts␈αcertain
␈↓ α∧␈↓puzzling␈αsentences␈αdiscussed␈αin␈αthe␈αphilosophical␈αliterature␈αcan␈αbe␈αneatly␈αexpressed␈αin␈αa␈αform␈αthat
␈↓ α∧␈↓permits␈α∪derivation␈α∩of␈α∪their␈α∪consequences.␈α∩ However,␈α∪the␈α∩motivation␈α∪for␈α∪the␈α∩work␈α∪is␈α∪AI␈α∩not
␈↓ α∧␈↓philosophy.

␈↓ α∧␈↓␈↓αMcCarthy,␈α⊃John␈α⊃(1980)␈↓:␈α⊃"Circumscription␈α∩-␈α⊃A␈α⊃Form␈α⊃of␈α⊃Non-Monotonic␈α∩Reasoning",␈α⊃␈↓↓Artificial
␈↓ α∧␈↓↓Intelligence␈↓, Volume 13, Numbers 1,2, April.

␈↓ α∧␈↓This␈αis␈αthe␈αmost␈αimportant␈αof␈αthe␈αsix␈αpapers␈αand␈αreports␈αand␈αthe␈αone␈αthat␈αhas␈αreceived␈αthe␈αmost
␈↓ α∧␈↓attention␈α∂from␈α∂other␈α∞scientists.␈α∂ The␈α∂need␈α∞for␈α∂non-monotonic␈α∂reasoning␈α∞in␈α∂AI␈α∂and␈α∂in␈α∞database
␈↓ α∧␈↓theory␈α⊃became␈α⊂apparent␈α⊃in␈α⊂the␈α⊃middle␈α⊂70s␈α⊃and␈α⊂several␈α⊃systems␈α⊂were␈α⊃proposed.␈α⊂ The␈α⊃issue␈α⊂of
␈↓ α∧␈↓␈↓↓Artificial␈α
Intelligence␈↓␈α
in␈α
which␈α
this␈α
paper␈α
appeared␈α
contains␈α
two␈α
other␈α
proposals.␈α
 I␈α
believe␈αthat
␈↓ α∧␈↓circumscription␈αis␈αthe␈αmost␈αsuccessful␈αof␈αthem.␈α Further␈αpapers␈αon␈αcircumscription␈αwere␈αwritten␈α
by
␈↓ α∧␈↓Raymond␈α∪Reiter␈α∪of␈α∪the␈α∪University␈α∪of␈α∪British␈α∪Columbia,␈α∪Jack␈α∪Minker␈α∪of␈α∪the␈α∪University␈α∪of
␈↓ α∧␈↓Maryland␈αand␈αVladimir␈αLifschitz␈αof␈αthe␈αUniversity␈αof␈αTexas␈αat␈αEl␈αPaso.␈α I␈αhave␈αa␈αnew␈αpaper␈αon
␈↓ α∧␈↓circumscription, but there is one problem I would like to solve before publishing it.

␈↓ α∧␈↓␈↓αMcCarthy,␈α
John␈α
(1982)␈↓:␈α
"Common␈α
Business␈α
Communication␈α
Language",␈α
in␈α∞␈↓↓Textverarbeitung␈α
und
␈↓ α∧␈↓↓B␈↓
:␈↓↓urosysteme␈↓,␈α
Albert␈αEndres␈α
and␈αJ␈↓
:␈↓urgen␈α
Reetz,␈αeds.␈α
 R.␈αOldenbourg␈α
Verlag,␈αMunich␈α
and␈αVienna
␈↓ α∧␈↓1982.

␈↓ α∧␈↓Since␈α⊃much␈α⊃office␈α⊃work␈α⊃consists␈α⊃in␈α⊃communicating␈α⊃with␈α⊃other␈α⊃organizations,␈α⊃increasing␈α⊃office
␈↓ α∧␈↓productivity␈α∞requires␈α
that␈α∞computers␈α
belonging␈α∞to␈α
different␈α∞organizations␈α
communicate␈α∞with␈α
one
␈↓ α∧␈↓another␈αabout␈αbusiness␈αmatters.␈α The␈αparadigm␈αcase␈αinvolves␈αa␈αcost␈αanalysis␈αprogram␈αgetting␈αbids
␈↓ α∧␈↓for␈αcomponents␈αfrom␈α
the␈αcomputers␈αbelonging␈αto␈α
potential␈αsuppliers.␈α The␈α
idea␈αstarted␈αas␈αa␈α
simple
␈↓ α∧␈↓proposal␈αfor␈αstandardization,␈αbut␈αit␈αturned␈αup␈αimportant␈αunsolved␈αproblems␈αin␈αthe␈αsemantics␈αand
␈↓ α∧␈↓␈↓ u2


␈↓ α∧␈↓pragmatics␈α∂of␈α∂natural␈α∂language.␈α⊂ Indeed␈α∂it␈α∂led␈α∂to␈α⊂the␈α∂conclusion␈α∂that␈α∂putting␈α⊂natural␈α∂language
␈↓ α∧␈↓front␈α⊂ends␈α∂on␈α⊂existing␈α∂programs␈α⊂is␈α∂the␈α⊂wrong␈α∂problem.␈α⊂ The␈α∂point␈α⊂isn't␈α∂to␈α⊂express␈α⊂in␈α∂natural
␈↓ α∧␈↓language␈αwhat␈αwe␈αalready␈αexpress␈αin␈αsome␈αkind␈αof␈αcomputerese,␈αbut␈αto␈αexpress␈αformally␈αconcepts,
␈↓ α∧␈↓facts and requests that have heretofore only been expressable in natural language.

␈↓ α∧␈↓␈↓αGabriel,␈α
Richard␈α
P.␈α
and␈α
John␈α
McCarthy␈α
(1984)␈↓:␈α
"Queue-based␈α
Multi-processing␈α∞Lisp",␈α
accepted
␈↓ α∧␈↓for publication in the proceedings of the 1984 Lisp Conference to be held in Austin in August.

␈↓ α∧␈↓Getting␈α
greater␈αperformance␈α
from␈α
computers␈αrequires␈α
parallelism,␈α
and␈αLISP␈α
has␈αtraditionally␈α
been
␈↓ α∧␈↓regarded␈αas␈αa␈αsomewhat␈αrecalcitrant␈αlanguage␈αfrom␈αthis␈αpoint␈αof␈αview.␈α The␈αpaper␈αcontains␈αa␈αfew
␈↓ α∧␈↓constructs␈αto␈αbe␈αadded␈αto␈αLISP␈αto␈αmake␈αefficient␈αuse␈αof␈αparallel␈αprocessors.␈α The␈αoriginal␈αversions
␈↓ α∧␈↓of␈αthe␈αideas␈αare␈αmine,␈αbut␈αtheir␈αsubsequent␈αdevelopment␈αand␈αall␈αthe␈αimplementation␈αwork␈αare␈αmy
␈↓ α∧␈↓co-author's.

␈↓ α∧␈↓␈↓αMcCarthy,␈αJohn␈α(1982)␈↓:␈α␈↓↓Coloring␈αMaps␈α
and␈αthe␈αKowalski␈αDoctrine␈↓,␈αReport␈αNo.␈α
STAN-CS-82-903,
␈↓ α∧␈↓Computer Science Department, Stanford University, Stanford, CA 94305.

␈↓ α∧␈↓Robert␈α
Kowalski,␈αwho,␈α
along␈α
with␈αAlain␈α
Colmerauer,␈α
originated␈αlogic␈α
programming,␈αexpressed␈α
the
␈↓ α∧␈↓doctrine␈α⊃"Algorithm␈α∩equals␈α⊃logic␈α⊃plus␈α∩control".␈α⊃ Several␈α⊃authors␈α∩(including␈α⊃Keith␈α∩Clark,␈α⊃Luis
␈↓ α∧␈↓Pereira␈α∩and␈α∪Herv␈↓
`␈↓e␈α∩Gallaire),␈α∩most␈α∪prominently␈α∩in␈α∩connection␈α∪with␈α∩logic␈α∪programming,␈α∩have
␈↓ α∧␈↓proposed␈α
formalisms␈α∞in␈α
which␈α∞logic␈α
and␈α∞control␈α
can␈α∞be␈α
expressed␈α∞separately.␈α
 The␈α∞advantage␈α
is
␈↓ α∧␈↓this.␈α The␈αlogic␈α
of␈αan␈αalgorithm␈α
can␈αoften␈αbe␈α
expressed␈αin␈αa␈α
simple␈αway␈αthat␈α
is␈αeasy␈αto␈α
understand
␈↓ α∧␈↓and␈α
in␈α
terms␈α
of␈α
which,␈αthe␈α
algorithm␈α
can␈α
be␈α
proved␈αto␈α
give␈α
the␈α
desired␈α
results.␈α However,␈α
efficient
␈↓ α∧␈↓execution␈αoften␈αrequires␈αcomplicated␈αcontrol.␈α It␈αseemed␈αto␈αme␈αthat␈αthe␈αcontrol␈αschemes␈αthat␈αhave
␈↓ α∧␈↓been␈αproposed␈αare␈αvery␈αlimited,␈αand␈α
that␈αthe␈αproblem␈αof␈αcoloring␈αmaps␈αpresents␈α
some␈αinteresting
␈↓ α∧␈↓problems␈αof␈αseparating␈αlogic␈αand␈αcontrol.␈α Both␈αthe␈αpostponement␈αcontrol␈αand␈αthe␈αKempe␈αcontrol
␈↓ α∧␈↓discussed␈α
in␈α
the␈αarticle␈α
have␈α
more␈αgeneral␈α
applications.␈α
 After␈αthe␈α
referenced␈α
report␈α
was␈αwritten,
␈↓ α∧␈↓further␈α∪work␈α∪done␈α∪during␈α∪a␈α∪visit␈α∪to␈α∪Kowalski␈α∪at␈α∪Imperial␈α∪College␈α∪resulted␈α∪in␈α∪a␈α∪notion␈α∪of
␈↓ α∧␈↓"introspective␈α
programming"␈αin␈α
which␈α
a␈αProlog␈α
program␈α
can␈αlook␈α
at␈α
its␈αown␈α
goal␈α
and␈αsearch␈α
trees.
␈↓ α∧␈↓A␈α∞small␈α∂"introspective␈α∞Prolog␈α∂interpreter"␈α∞was␈α∞implemented␈α∂by␈α∞Peter␈α∂Szeredi␈α∞of␈α∂the␈α∞Hungarian
␈↓ α∧␈↓Academy␈α⊗of␈α↔Sciences,␈α⊗and␈α⊗publication␈α↔of␈α⊗the␈α↔paper␈α⊗awaits␈α⊗incorporation␈α↔of␈α⊗the␈α↔idea␈α⊗of
␈↓ α∧␈↓introspection and reference to Szeredi's (unpublished) work.

␈↓ α∧␈↓␈↓αMcCarthy,␈α→John␈α_(1984)␈↓:␈α→"Applications␈α_of␈α→Circumscription␈α_to␈α→Formalizing␈α→Common␈α_Sense
␈↓ α∧␈↓Knowledge".␈α∪ This␈α∪is␈α∪has␈α∪been␈α∪submitted␈α∪to␈α∪the␈α∪1984␈α∪AAAI␈α∪conference␈α∪on␈α∪non-monotonic
␈↓ α∧␈↓reasoning,␈αwhich␈αwill␈αnot␈αhave␈αa␈αproceedings␈αand␈αis␈αbeing␈αsubmitted␈αfor␈αpublication␈αto␈α␈↓↓Artificial
␈↓ α∧␈↓↓Intelligence␈↓.

␈↓ α∧␈↓Abstract:␈α
We␈α
present␈α
a␈α
new␈α
and␈α
more␈αsymmetric␈α
version␈α
of␈α
the␈α
circumscription␈α
method␈α
of␈αnon-
␈↓ α∧␈↓monotonic␈α∀reasoning␈α∃(McCarthy␈α∀1980)␈α∃and␈α∀some␈α∀applications␈α∃to␈α∀formalizing␈α∃common␈α∀sense
␈↓ α∧␈↓knowledge.␈α⊃ The␈α⊃applications␈α⊃in␈α⊃this␈α⊃paper␈α⊃are␈α⊃based␈α⊃on␈α⊃minimizing␈α⊃the␈α⊃abnormality␈α∩of␈α⊃the
␈↓ α∧␈↓different␈α∞aspects␈α∞of␈α
a␈α∞situation.␈α∞ Included␈α
are␈α∞non-monotonic␈α∞treatments␈α
of␈α∞␈↓↓is-a␈↓␈α∞hierarchies,␈α
the
␈↓ α∧␈↓unique names hypothesis, and the frame problem.

␈↓ α∧␈↓I␈α
mistakenly␈α∞delayed␈α
submitting␈α∞this␈α
proposal␈α∞until␈α
this␈α∞paper␈α
was␈α∞completed.␈α
 Naturally␈α∞it␈α
took
␈↓ α∧␈↓longer than expected.



␈↓ α∧␈↓Proposed Research
␈↓ α∧␈↓␈↓ u3


␈↓ α∧␈↓␈↓ αTAs␈αthe␈αsubmitted␈αpapers␈αshow,␈αI␈αhave␈αbeen␈αactive␈αin␈αa␈αvariety␈αof␈αfields␈αof␈αcomputer␈αscience
␈↓ α∧␈↓and will continue to work on ideas that occur to me.

␈↓ α∧␈↓␈↓ αTHowever,␈α∪the␈α∪main␈α∪long␈α∪term␈α∪goal␈α∪of␈α∪my␈α∪research␈α∪has␈α∪always␈α∪been␈α∪to␈α∪find␈α∪ways␈α∩of
␈↓ α∧␈↓formalizing␈αcommon␈αsense␈αknowledge␈αand␈αreasoning␈αability␈αso␈αthat␈αa␈αcomputer␈αprogram␈αcan␈αhave
␈↓ α∧␈↓the common sense knowledge and the common sense ability to achieve the goals we give it.

␈↓ α∧␈↓␈↓ αTWe␈α∃distinguish␈α∃common␈α∀sense␈α∃knowledge␈α∃and␈α∀common␈α∃sense␈α∃ability.␈α∃ Common␈α∀sense
␈↓ α∧␈↓knowledge␈α⊂includes␈α⊂facts␈α⊂about␈α⊃how␈α⊂events␈α⊂occur␈α⊂in␈α⊂time,␈α⊃about␈α⊂the␈α⊂effects␈α⊂of␈α⊂actions␈α⊃by␈α⊂the
␈↓ α∧␈↓knower␈αand␈αothers,␈αfacts␈αabout␈αthe␈αrelation␈αbetween␈αphenomena␈αin␈αthe␈αworld␈αand␈αwhat␈α
a␈αperson
␈↓ α∧␈↓or␈αprogram␈αwith␈αsensory␈αcapabilities␈αcan␈αlearn␈α
about␈αit,␈αfacts␈αabout␈αphysical␈αobjects␈αand␈αhow␈α
they
␈↓ α∧␈↓are␈α
perceived,␈αand␈α
about␈α
their␈αproperties␈α
and␈αtheir␈α
relations␈α
to␈αone␈α
another.␈α An␈α
example␈α
is␈αthe
␈↓ α∧␈↓fact␈αthat␈αeggs␈αcontain␈αa␈αyolk␈αand␈αa␈αwhite␈αand␈α
a␈αshell,␈αhow␈αto␈αrecognize␈αan␈αegg,␈αthe␈αeffects␈αof␈α
hard
␈↓ α∧␈↓boiling␈α∩them␈α∩and␈α∩the␈α∪effects␈α∩of␈α∩dropping␈α∩them.␈α∩ Common␈α∪sense␈α∩ability␈α∩involves␈α∩the␈α∪use␈α∩of
␈↓ α∧␈↓common␈αsense␈αknowledge␈αand␈αthe␈αobservation␈αof␈αthe␈αworld␈αto␈αdecide␈αwhat␈αto␈αdo␈αto␈αachieve␈αone's
␈↓ α∧␈↓goals.␈α The␈α"common"␈αin␈α"common␈αsense"␈αrefers␈αto␈αthe␈αfact␈αthat␈αa␈αlarge␈αamount␈αof␈αthis␈αknowledge
␈↓ α∧␈↓and␈αability␈αis␈αcommon␈αto␈αall␈αhumans.␈α Not␈α
much␈αof␈αit␈αis␈αunderstood␈αwell␈αenough␈αto␈αinclude␈α
it␈αin
␈↓ α∧␈↓computer programs.

␈↓ α∧␈↓␈↓ αTExpressing␈α↔common␈α⊗sense␈α↔knowledge␈α⊗in␈α↔languages␈α⊗of␈α↔mathematical␈α⊗logic␈α↔and␈α⊗using
␈↓ α∧␈↓controlled␈α∂deduction␈α∂as␈α∂a␈α∂way␈α∂of␈α∂deciding␈α∂what␈α∂to␈α∂do␈α∂was␈α∂first␈α∂proposed␈α∂in␈α⊂(McCarthy␈α∂1960).
␈↓ α∧␈↓This␈α
proved␈α
very␈α
difficult␈αand␈α
progress␈α
was␈α
slow.␈α Many␈α
people␈α
gave␈α
up␈αon␈α
using␈α
logic␈α
in␈αAI␈α
and
␈↓ α∧␈↓proposed␈α∂other␈α∂formalisms,␈α∞but␈α∂in␈α∂the␈α∂main␈α∞they␈α∂proved␈α∂to␈α∂be␈α∞equivalent␈α∂to␈α∂subsets␈α∂of␈α∞logical
␈↓ α∧␈↓languages, and much attention in AI has returned to logic.

␈↓ α∧␈↓␈↓ αTA␈αmajor␈αadvance␈αin␈αthe␈αuse␈αof␈αlogical␈αlanguages␈αfor␈αAI␈αwas␈αthe␈αnotion␈αof␈αformalized␈αnon-
␈↓ α∧␈↓monotonic␈α∞reasoning␈α∞which␈α∞arose␈α∞in␈α∞the␈α∞middle␈α∞1970s.␈α∞ My␈α∞proposal␈α∞was␈α∞called␈α∞circumscription
␈↓ α∧␈↓(McCarthy␈α⊃1980).␈α⊃ A␈α⊃preliminary␈α⊃version␈α⊃under␈α⊂the␈α⊃name␈α⊃␈↓↓minimal␈α⊃inference␈↓␈α⊃was␈α⊃included␈α⊂in
␈↓ α∧␈↓(McCarthy 1977).

␈↓ α∧␈↓␈↓ αTThe␈α∞idea␈α
of␈α∞non-monotonic␈α
reasoning␈α∞and␈α
the␈α∞circumscription␈α
approach␈α∞to␈α∞formalizing␈α
it
␈↓ α∧␈↓seem␈α∩to␈α∩have␈α⊃wider␈α∩applicability␈α∩than␈α⊃was␈α∩previously␈α∩envisioned.␈α⊃ We␈α∩plan␈α∩to␈α∩continue␈α⊃our
␈↓ α∧␈↓previous␈α∞investigations␈α∞of␈α∞formalizing␈α∞common␈α
sense␈α∞knowledge␈α∞using␈α∞circumscription␈α∞as␈α∞a␈α
tool.
␈↓ α∧␈↓However,␈α⊂there␈α⊂seem␈α∂to␈α⊂be␈α⊂many␈α⊂new␈α∂applications␈α⊂in␈α⊂AI␈α∂but␈α⊂also␈α⊂in␈α⊂databases,␈α∂programming
␈↓ α∧␈↓languages␈αand␈αeven␈αin␈αanalytic␈αphilosophy.␈α Our␈αchief␈αobjective␈αin␈αthe␈αnext␈αthree␈αyears␈αwill␈αbe␈αto
␈↓ α∧␈↓explore these new possibilities.  Here are some of them.

␈↓ α∧␈↓Formalization of common sense

␈↓ α∧␈↓␈↓ αTFor␈α
a␈α
long␈α
time,␈α
the␈α
lack␈α∞of␈α
formalized␈α
non-monotonic␈α
reasoning␈α
has␈α
impeded␈α∞the␈α
formal
␈↓ α∧␈↓expression␈α∩of␈α∪common␈α∩sense␈α∪knowledge␈α∩and␈α∩writing␈α∪programs␈α∩that␈α∪carry␈α∩out␈α∪common␈α∩sense
␈↓ α∧␈↓reasoning.␈α This␈α
situation␈αhas␈αbeen␈α
somewhat␈αrelieved␈α
by␈αthe␈αadvent␈α
of␈αcircumscription␈αand␈α
other
␈↓ α∧␈↓non-monotonic␈α⊃reasoning␈α⊃systems.␈α⊂ In␈α⊃particular␈α⊃the␈α⊂circumscription␈α⊃formulation␈α⊃of␈α⊃the␈α⊂frame
␈↓ α∧␈↓problem of (McCarthy 1984) seems to me to be satisfactory.

␈↓ α∧␈↓␈↓ αTTherefore,␈α
it␈α
seems␈α∞to␈α
be␈α
time␈α∞to␈α
extend␈α
the␈α
formalization␈α∞of␈α
common␈α
sense␈α∞knowledge␈α
to
␈↓ α∧␈↓some␈α⊂new␈α⊂domains.␈α⊃ I␈α⊂have␈α⊂the␈α⊂following␈α⊃in␈α⊂mind,␈α⊂but␈α⊂the␈α⊃subject␈α⊂is␈α⊂now␈α⊃exciting␈α⊂increased
␈↓ α∧␈↓interest among graduate students, so it may be possible to do more.
␈↓ α∧␈↓␈↓ u4


␈↓ α∧␈↓␈↓ αT1.␈αThe␈αblocks␈αworld␈αwith␈αincomplete␈αexpression␈αof␈αthe␈αresults␈αof␈αaction.␈α All␈αformalizations
␈↓ α∧␈↓of␈αthe␈αblocks␈αworld␈αthat␈αI␈αknow␈αabout,␈αincluding␈αthose␈αin␈αthe␈αliterature␈αon␈αplanning,␈αuse␈αcomplete
␈↓ α∧␈↓rules.␈α
 Namely,␈α
the␈α
result␈α
of␈α
an␈α∞action␈α
is␈α
fully␈α
described.␈α
 However,␈α
common␈α
sense␈α∞knowledge␈α
of
␈↓ α∧␈↓the␈αeffects␈αof␈αaction␈αis␈αoften␈αincomplete␈αin␈αmany␈αrespects.␈α For␈αexample,␈αwe␈αknow␈αthat␈αwhen␈αblock
␈↓ α∧␈↓A␈α∩is␈α∩placed␈α⊃on␈α∩block␈α∩B,␈α⊃A␈α∩will␈α∩be␈α⊃on␈α∩B␈α∩in␈α⊃the␈α∩resulting␈α∩situation,␈α⊃but␈α∩neither␈α∩our␈α⊃verbal
␈↓ α∧␈↓expression␈α∂of␈α∂such␈α∞rules␈α∂nor␈α∂our␈α∞informal␈α∂knowledge␈α∂formulates␈α∞where␈α∂on␈α∂B,␈α∞block␈α∂A␈α∂will␈α∞be.
␈↓ α∧␈↓Rather␈α∂than␈α∞devise␈α∂a␈α∞language␈α∂for␈α∞expressing␈α∂the␈α∞precise␈α∂location␈α∞of␈α∂one␈α∞block␈α∂on␈α∂another␈α∞we
␈↓ α∧␈↓need␈α∞to␈α∂formalize␈α∞the␈α∂common␈α∞sense␈α∂knowledge␈α∞about␈α∞this␈α∂that␈α∞people␈α∂and␈α∞robots␈α∂with␈α∞similar
␈↓ α∧␈↓opportunities to observe can actually have.

␈↓ α∧␈↓␈↓ αT2.␈α
A␈α
problem␈α
in␈α
which␈α
a␈α
person␈α
achieves␈α
a␈α
goal␈α
by␈α
asking␈α
another␈α
person␈α
for␈αhelp,␈α
knowing
␈↓ α∧␈↓that␈αthe␈αother␈αperson␈αis␈αwilling␈αand␈αcan␈αhelp␈αin␈αthe␈αmanner␈αdesired.␈α This␈αexample␈αadmits␈αmany
␈↓ α∧␈↓non-monotonic␈αshortcuts,␈αwhich␈αare␈αoften␈αimportant␈αin␈αpractice.␈α For␈αexample,␈αit␈αcan␈αbe␈αtaken␈αas
␈↓ α∧␈↓standard␈αthat␈α
a␈αperson␈α
knows␈αwhat␈α
he␈αcan␈αdo.␈α
 The␈αcontrary␈α
is␈αan␈α
abnormality.␈α We␈α
propose␈αto
␈↓ α∧␈↓formalize␈α
the␈αcommon␈α
sense␈αknowledge␈α
of␈αhow␈α
to␈αachieve␈α
goals␈αthat␈α
require␈αthe␈α
co-operation␈αof
␈↓ α∧␈↓other agents.

␈↓ α∧␈↓␈↓ αT3.␈αPerhaps␈αthe␈αmost␈αobvious␈αalmost␈αuntouched␈αproblem␈αfor␈αformalization␈αof␈αcommon␈αsense
␈↓ α∧␈↓knowledge␈α⊃concerns␈α⊃concurrent␈α⊃processes.␈α⊃ The␈α⊃formalizations␈α⊃of␈α⊃concurrent␈α⊃processes␈α∩used␈α⊃in
␈↓ α∧␈↓studying␈α⊂parallel␈α⊃computation␈α⊂are␈α⊃mostly␈α⊂irrelevant,␈α⊃because␈α⊂they␈α⊃concern␈α⊂processes␈α⊃which␈α⊂the
␈↓ α∧␈↓theorist␈α~has␈α~the␈α~privilege␈α~of␈α~designing.␈α~ The␈α~designs␈α~make␈α~much␈α~of␈α~the␈α~problem␈α~of
␈↓ α∧␈↓synchronization,␈α≠but␈α~this␈α≠is␈α≠little␈α~considered␈α≠in␈α≠common␈α~sense␈α≠reasoning.␈α≠ Thus␈α~when
␈↓ α∧␈↓contemplating␈α
walking␈α
down␈α∞a␈α
corridor␈α
a␈α
person␈α∞doesn't␈α
plan␈α
in␈α
advance␈α∞how␈α
he␈α
and␈α∞a␈α
person
␈↓ α∧␈↓going the other way are to avoid permanently blocking each other.

␈↓ α∧␈↓␈↓ αT4.␈α⊃We␈α⊃propose␈α⊃to␈α⊂continue␈α⊃our␈α⊃previous␈α⊃work␈α⊂in␈α⊃formalizing␈α⊃knowledge␈α⊃about␈α⊂people's
␈↓ α∧␈↓knowledge.␈α
 Some␈α
of␈α
it␈α
is␈α
in␈α
(McCarthy,␈α∞Sato,␈α
Igarashi␈α
and␈α
Hayashi␈α
1977),␈α
but␈α
most␈α
of␈α∞it,␈α
some
␈↓ α∧␈↓quite␈αold,␈αis␈αstill␈αunpublished.␈α Recently␈αRon␈αFagin,␈αJoe␈αHalpern,␈αMoshe␈αVardi␈αof␈αIBM␈αSan␈αJose
␈↓ α∧␈↓and␈α
Yoram␈α
Moses␈α
of␈α
my␈α
group␈α
have␈α
begun␈α
new␈α
work␈α
in␈α
the␈α
subject␈α
that␈α
makes␈α
further␈αpursuit␈α
of
␈↓ α∧␈↓my old ideas more promising.


␈↓ α∧␈↓Mathematical problems of non-monotonic reasoning

␈↓ α∧␈↓␈↓ αTCircumscription␈α∂presents␈α∂many␈α∞problems␈α∂of␈α∂a␈α∞mathematical␈α∂logical␈α∂nature␈α∂whose␈α∞solution
␈↓ α∧␈↓will␈α⊂be␈α⊃important␈α⊂for␈α⊃applications.␈α⊂ Here␈α⊂are␈α⊃some␈α⊂on␈α⊃which␈α⊂I␈α⊂propose␈α⊃to␈α⊂work.␈α⊃ An␈α⊂invited
␈↓ α∧␈↓address␈α⊂to␈α⊂a␈α⊂meeting␈α⊂of␈α⊂the␈α⊂Association␈α∂for␈α⊂Symbolic␈α⊂Logic␈α⊂in␈α⊂January␈α⊂1985␈α⊂will␈α⊂provide␈α∂an
␈↓ α∧␈↓opportunity␈α_to␈α_present␈α_a␈α_few␈α_results␈α↔but␈α_mostly␈α_to␈α_attract␈α_the␈α_attention␈α_of␈α↔professional
␈↓ α∧␈↓mathematical logicians to this important new domain.

␈↓ α∧␈↓␈↓ αT1.␈αWhen␈αis␈αthe␈αsecond␈αorder␈αformula␈αof␈αcircumscription␈αequivalent␈αto␈αa␈αfirst␈αorder␈α
formula?
␈↓ α∧␈↓This␈αis␈αtrue␈αof␈αall␈α
but␈αone␈αof␈αthe␈αexamples␈αof␈α
(McCarthy␈α1980),␈αand␈αsome␈αgeneral␈α
partial␈αresults
␈↓ α∧␈↓have been obtained by me and by Vladimir Lifschitz of the University of Texas at El Paso.

␈↓ α∧␈↓␈↓ αT2.␈α⊃Can␈α⊃Reiter's␈α⊂(1980)␈α⊃"unique␈α⊃names␈α⊃hypothesis"␈α⊂be␈α⊃expressed␈α⊃non-monotonically␈α⊃by␈α⊂a
␈↓ α∧␈↓second␈α∂order␈α∂formula?␈α∂ It␈α∂can␈α∂be␈α∂done␈α∂with␈α∂circumscription␈α∂provided␈α∂that␈α∂names␈α∂are␈α⊂the␈α∂only
␈↓ α∧␈↓objects␈α⊂in␈α⊂the␈α⊃theory,␈α⊂but␈α⊂this␈α⊂seems␈α⊃undesirable.␈α⊂ There␈α⊂seems␈α⊂to␈α⊃be␈α⊂a␈α⊂relation␈α⊃between␈α⊂this
␈↓ α∧␈↓problem and the notion of a figure being in general position.
␈↓ α∧␈↓␈↓ u5


␈↓ α∧␈↓␈↓ αT3.␈α
In␈α∞many␈α
cases␈α
circumscription␈α∞formulas␈α
"compile"␈α
rather␈α∞directly␈α
into␈α∞executable␈α
Prolog
␈↓ α∧␈↓programs.␈α∩ It␈α∩is␈α∩important␈α∪to␈α∩know␈α∩when␈α∩this␈α∩is␈α∪the␈α∩case␈α∩and␈α∩when␈α∩the␈α∪implementation␈α∩of
␈↓ α∧␈↓circumscription requires different mechanisms.

␈↓ α∧␈↓␈↓ αT4.␈αIn␈αwhat␈α
cases␈αis␈αthe␈α
question␈αof␈αwhether␈αa␈α
sentence␈αis␈αimplied␈α
by␈αthe␈αcircumscription␈αof␈α
a
␈↓ α∧␈↓set␈α∞of␈α∞sentences␈α∂decidable?␈α∞ It␈α∞is␈α∂true␈α∞in␈α∞the␈α∂propositional␈α∞case␈α∞and␈α∂when␈α∞all␈α∞the␈α∂predicates␈α∞are
␈↓ α∧␈↓monadic.␈α
 This␈αsuggests␈α
exploring␈αanalogs␈α
of␈αthe␈α
decidable␈αcases␈α
of␈αthe␈α
first␈αorder␈α
logic␈αdecision
␈↓ α∧␈↓problem.␈α↔ However,␈α⊗the␈α↔propositional␈α↔case␈α⊗already␈α↔corresponds␈α↔to␈α⊗a␈α↔tree␈α↔of␈α⊗propositional
␈↓ α∧␈↓satisfaction␈α↔problems,␈α↔so␈α↔circumscriptive␈α↔inferability␈α⊗is␈α↔likely␈α↔to␈α↔be␈α↔harder␈α↔than␈α⊗ordinary
␈↓ α∧␈↓deducibility.  Additional references beyond those listed in the accomplishments section.

␈↓ α∧␈↓␈↓αLifschitz, Vladimir␈↓(1983): unpublished note on circumscription

␈↓ α∧␈↓␈↓αMcCarthy,␈α∂John␈α∂(1977)␈↓:␈α∂"Epistemological␈α∂Problems␈α∂of␈α∂Artificial␈α∂Intelligence",␈α∂␈↓↓Proceedings␈α∂of␈α∞the
␈↓ α∧␈↓↓Fifth␈α~International␈α~Joint␈α~Conference␈α~on␈α~Artificial␈α~Intelligence␈↓,␈α~M.I.T.,␈α~Cambridge,␈α→Mass.
␈↓ α∧␈↓ijcai.c[e77,jmc]

␈↓ α∧␈↓␈↓αReiter, Raymond (19xx)␈↓: (concerning unique names)

␈↓ α∧␈↓␈↓αReiter,␈α!Raymond␈α!(1982)␈↓:␈α""Circumscription␈α!Implies␈α!Predicate␈α"Completion␈α!(Sometimes)",
␈↓ α∧␈↓Proceedings of the National Conference on Artificial Intelligence, AAAI-82.